package ar.uba.fi.tonyvaliente.tree;

import java.util.LinkedList;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;

import ar.uba.fi.tonyvaliente.utils.Pair;

public class BTreeIterator<K extends Comparable<K>, V> implements Iterator<Pair<K,V>> {
	
	private LinkedList<BTreeNode<K,V>> pilaNodos;
	private LinkedList<Integer> pilaContadores;
	private Iterator<Map.Entry<K,V>> actualNodeKeys;
	
	public BTreeIterator(BTree<K,V> tree) {
		this.pilaNodos = new LinkedList<BTreeNode<K,V>>();
		this.pilaContadores = new LinkedList<Integer>();
		this.actualNodeKeys = null;
		
		pilaNodos.addFirst(tree.rootNode);
		pilaContadores.addFirst(0);
	}

	@Override
	public boolean hasNext() {
		if (!pilaNodos.isEmpty()) {
			LinkedList<BTreeNode<K,V>> otraPilaNodos;
			LinkedList<Integer> otraPilaContadores; 
			boolean hayProximo;
			boolean verifiqueRefsEnTop;
			
			otraPilaNodos = new LinkedList<BTreeNode<K,V>>(pilaNodos);
			otraPilaContadores = new LinkedList<Integer>(pilaContadores);
			hayProximo = false;
			verifiqueRefsEnTop = false;
			
			BTreeNode<K,V> top; 
			Integer i;
			List<BReference<K,V>> refs;
			
			do {
				i = otraPilaContadores.getFirst(); 
				top = otraPilaNodos.getFirst();
				refs = top.getReferences();
				eraseNullReferences(refs);
				
				hayProximo = (i < top.getDatos().size())
					|| (!verifiqueRefsEnTop && refs.size() > 0
							&& i < refs.size()
							&& refs.get(i) != null);
				
				verifiqueRefsEnTop = true;
				
				if (!hayProximo && !otraPilaNodos.isEmpty()) {
					otraPilaNodos.removeFirst();
					otraPilaContadores.removeFirst();
					if (!otraPilaNodos.isEmpty()) {
						i = otraPilaContadores.getFirst();
						top = otraPilaNodos.getFirst();
						refs = top.getReferences();
						eraseNullReferences(refs);
					}
				}
			} while (!hayProximo && !otraPilaNodos.isEmpty());
			return hayProximo;
		} else {
			return false;
		}
	}

	@Override
	public Pair<K,V> next() {
		if (!pilaNodos.isEmpty()) {
			try {
				Integer i;
				BTreeNode<K,V> top;
				List<BReference<K,V>> refs;
				
				i = pilaContadores.getFirst();
				top = pilaNodos.getFirst();
				refs = top.getReferences();
				eraseNullReferences(refs);
				
				if (i < top.getDatos().size()) {
					while (refs.size() > 0 &&refs.get(i) != null) {
						pilaNodos.addFirst(refs.get(i).getNode());
						pilaContadores.addFirst(0);
						i = pilaContadores.getFirst();
						top = pilaNodos.getFirst();
						refs = top.getReferences();
						eraseNullReferences(refs);
					}
				} else {
					if (i == refs.size()-1 && refs.size() > 0) {
						while (refs.size() > 0 && refs.get(i) != null) {
							pilaNodos.addFirst(refs.get(i).getNode());
							pilaContadores.addFirst(0);
							i = pilaContadores.getFirst();
							top = pilaNodos.getFirst();
							refs = top.getReferences();
							eraseNullReferences(refs);
						}
					} else {
						do {
							pilaNodos.removeFirst();
							pilaContadores.removeFirst();
							top = pilaNodos.getFirst();
							i = pilaContadores.getFirst();
							refs = top.getReferences();
							eraseNullReferences(refs);
						} while (! pilaNodos.isEmpty() && i == top.getDatos().size());
					}
				}
				
				if (!pilaNodos.isEmpty()) {
					actualNodeKeys = top.getDatos().entrySet().iterator();
					for (int j = 0; j < i; j++) {
						actualNodeKeys.next();
					}
					i++;
					pilaContadores.set(0, i);
					Map.Entry<K, V> next = actualNodeKeys.next(); 
					return new Pair<K,V>(next.getKey(), next.getValue()); 
				} else {
					throw new NoSuchElementException("Ya se llego al final del BTree");
				}
			} catch (BTreeException e) {
				throw new RuntimeException(e);
			}
		} else {
			throw new NoSuchElementException("Ya se llego al final del BTree");
		}
	}

	@Override
	public void remove() {
		throw new UnsupportedOperationException("No se permite borrar "
				+ "elementos de un BTree mediante su Iterator");
	}
	
	private void eraseNullReferences(List<BReference<K,V>> refs) {
		Iterator<BReference<K,V>> it = refs.iterator();
		while (it.hasNext()) {
			if (it.next() == null) {
				it.remove();
			}
		}
	}

}
